package org.example.likou150.searchTree;
// https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?envType=study-plan-v2&envId=top-interview-150
// 思路：中序遍历 记录递归次数取值
public class KthSmallest {

    int index = 1;
    public int kthSmallest(TreeNode root, int k) {
        if(root==null){
            return -1;
        }
        int leftIndex = kthSmallest(root.left, k);

        if(index++ == k){
            return root.val;
        }

        int rightIndex = kthSmallest(root.right, k);

        return leftIndex!=-1? leftIndex:rightIndex;
    }

    private static class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
}
